# -*- coding:utf-8 -*-

# 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

# 示例:
# 输入: n = 4, k = 2
# 输出:
# [
#   [2,4],
#   [3,4],
#   [2,3],
#   [1,2],
#   [1,3],
#   [1,4],
# ]

#    3     3 +   2
#  C 5 = C 4 + C 3
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        def delCombin(n, k, add):
            if n == k:
                return [[i + 1 for i in xrange(k)] + add]
            if k == 1:
                ret = []
                for i in xrange(n):
                    ret.append([i + 1] + add)
                return ret
            return delCombin(n - 1, k, add) + delCombin(n - 1, k - 1, add + [n]) 
        
        return delCombin(n, k, [])
            

t = Solution()
print(t.combine(5,3))